package main

import "fmt"

/**
二分查找 时间复杂度 O(log n)
*/
func main() {
	//数组是排好序的
	arr := []int{1, 2, 3, 4, 7, 8, 9, 11, 12}
	fmt.Println(binarySearch(arr, 1))
}

func binarySearch(arr []int, goal int) int {
	//数组为空，或者目标值超出边界值
	if len(arr) == 0 || goal<arr[0] || goal>arr[len(arr)-1]{
		return -1
	}
	l := 0            //左侧端点索引
	r := len(arr) - 1 //右侧端点索引
	for l <= r {
		m := l + (r-l)/2 //中间位置

		//中间值大于目标值
		if arr[m] > goal {
			r = m - 1  //左侧游标置位中间值前一位
		} else if arr[m] < goal {
			l = m + 1 //右侧游标置位中间值后一位
		} else {
			return m  //找到了
		}

	}

	//没找到
	return -1
}
